Problems arise when it becomes necessary or desirable to quantize digital image data, such as when one wishes to display 24-bit encoded RGB image data on a 12-bit RGB display. Problems also occur due to the presence of block boundaries in connection with the encoding of a digital image using a block-based transform coding (for example, JPEG, H.263, MPEG-4, etc.).
Digital images are typically coded using a 24-bit RGB color palette, where each of the RGB channels is coded with eight bits. This coding scheme yields 256 levels of intensity for each of the red, green and blue channels, and a total of 2563=16777216 different colors, a number that is usually more than sufficient to represent all of the colors in the visible spectrum. However, in some cases the image data is to be represented using a display with, for example, only a 12-bit color palette (3*4-bits/channel or 16 levels of intensity per RGB channel). A fast (and low-quality) technique to convert the 24-bit RGB image to 12 bits simply linearly quantizes the 256 levels to 16 levels, by using the following equations:R4bit(x,y)=R8bit(x,y)>>4G4bit(x,y)=G8bit(x,y)>>4, where x and y are the image coordinatesB4bit(x,y)=B8bit(x,y)>>4
It can readily be shown that a result of such a linear 24-bit to 12-bit quantization is a limited number of colors and the presence of objectionable block artifacts in the resulting displayed image.
A typical technique to improve the subjective quality of the palette quantization process is to use color dithering. Although there are numerous different color dithering techniques, all of them are based on the same general idea: if two pixels with slightly different colors are viewed from a distance, the eye sees them as one pixel, whose color is an average of the two colors. As an example, FIG. 1 illustrates a grey-scale ramp that is represented using two colors and dithering.
Thus, in color dithering the colors that are missing from the quantized palette are simulated by alternating between two neighboring colors. This alternating between two colors can be done in various ways, such as by adding a fixed dithering noise pattern, also referred to as “ordered dithering”, or by adding a random dithering noise pattern (white noise or high frequency noise, also called blue noise) to each of the RGB channels before quantization, where the maximum amplitude of dithering noise values is one half of the quantization step. The following equations describe the process for 24-bit to 12-bit conversion. In practice, the results for each channel would be clipped to lie in the range of zero to 15.R4bit(x,y)=(R8bit(x,y)+noiseR(x,y))>>4G4bit(x,y)=(G8bit(x,y)+noiseG(x,y))>>4, where (−8<noiseR,G,B(x,y)<8)B4bit(x,y)=(B8bit(x,y)+noiseB(x,y))>>4
By the use of, for example, a fixed 2×2 pixel dithering noise pattern the apparent number of colors is increased as compared to the linear quantization approach, and the objectionable block artifacts in the resulting displayed image are slightly less visible.
However, neither of these approaches is optimum, as the resulting displayed images still contain objectionable block artifacts, and the range of apparent colors is still not optimum.
Those skilled in the art will recognize that the foregoing description of dithering is greatly simplified. For example, also well known is the error diffusion model that attempts to minimize, by using an error filter feedback approach, the error diffused by the noise in the image. Examples of suitable filters for implementing this approach are the Floyd-Steinberg, the Jarvis-Judice-Ninke, the Stucki and the Stevenson.
The above mentioned ordered dithering approach compares the original patterns from the image to a predetermined periodic array, where the coefficients of the array are the thresholds (which are known a priori and are thus “ordered”). The ordered dithering method is divided generally into two classes: dispersed (typically used in visual, e.g., computer, displays) and clustered (typically used in printers).
While the thresholding quantization and white noise techniques typically have the fastest execution times, as compared to the ordered dithering and the error diffusion approaches, they generally produce an inferior image to that produced by the ordered dithering and the error diffusion approaches.
Important factors when selecting a dithering method are the speed of execution (computational complexity), when considering the size of the display (i.e., the number of pixels) and the processing capabilities of the available data processor(s), as well as the visual quality of the resulting displayed image. Related to execution speed and computational complexity is the power consumption, particularly in the case of portable battery powered devices such as mobile (cellular) telephones, personal digital assistants, personal communicators and the like. The issue of power consumption will become even more important in modern cellular telephones, as multimedia standards are evolving to enable these devices to receive and display color video and other image data, such as image data obtained through a wireless packet data link from the Internet. However, these devices typically have a smaller display that is less capable than the high resolution displays found in computer graphics and other types of terminals, resulting in a need to quantize the received image data to accommodate the lower resolution display. The use of quantization, however, will lead to reductions in image quality and thus to a requirement to apply dithering in order to enhance the quality of the displayed image. As such, it can be realized that a need has arisen to provide an improved dithering technique that overcomes the foregoing and other problems that exist in currently available dithering techniques.